using namespace std;
#include<vector>
#include<unordered_map>
#include<string>

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            int aim = target - nums[i];
            if (hash.count(aim)) return { hash[aim], i };
            else
                hash[nums[i]] = i;
        }

        return { -1, -1 };
    }
};



struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* cur1 = l1, * cur2 = l2;
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;

        int t = 0;
        while (cur1 || cur2 || t)
        {
            if (cur1)
            {
                t += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2)
            {
                t += cur2->val;
                cur2 = cur2->next;
            }
            int x = t % 10;
            ListNode* node = new ListNode(x);
            prev->next = node;
            prev = node;
            t /= 10;
        }

        prev = newhead->next;
        delete newhead;
        return prev;
    }
};


class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int hash[128] = { 0 };
        int len = INT_MIN;
        for (int left = 0, right = 0; right < n; right++)
        {
            char ch = s[right];
            hash[ch]++;
            while (hash[ch] > 1)
            {
                hash[s[left++]]--;
            }
            len = max(len, right - left + 1);
        }

        return len == INT_MIN ? 0 : len;
    }
};


class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int tmp = 0;
        string ret;
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }

                if (dp[i][j])
                {
                    if (j - i + 1 > tmp)
                    {
                        tmp = j - i + 1;
                        ret = s.substr(i, tmp);
                    }
                }
            }
        }

        return ret;
    }
};